6 분 소요

image


Heap : Priority Queue

image


Priority Queue

  • Queue
    • Queue에 삽입된(도착 시간) 순서에 기반을 둠
    • FIFO 혹은 FCFS 기반의 서비스 제공
  • Priority(우선순위) Queue
    • 더 일반적인 우선 순위에 기반을 둠
    • 우선 순위의 예 : 직급, 중요도, 긴급도, 수행시간, 등
    • (도착한 순서에는 상관없이) 우선 순위에 근거하여 서비스 제공
  • 응용 예 :
    • Job scheduling (OS)
    • Military, Emergency


  • Priority Queue : Find_Max (Min)
    • Queue의 각 element는 priority 값 (Key 라고 지칭)을 가짐.
    • Priority (혹은 key)는 보통 정수(integer) 값으로 표현.
    • 가장 큰 정수 값 (예: 중요도)을 갖는 element가 먼저 delete 되는 경우, 이를 Max Priority Queue라고 함.
    • 가장 작은 정수 값 (예: 수행시간)을 갖는 element가 먼저 delete 되는 경우, 이를 Min Priority Queue라고 함.
    • 즉, Priority Queue의 핵심은 Maximum (혹은 Minimum) 값을 갖는 key를 찾는 문제.


Priority Queue의 구현

  • Unordered Array
  • Ordered Array
  • Unordered Linked List
  • Ordered Linked List
  • Binary Search Tree
  • Max Heap (Min Heap)


  • Unordered Array를 이용
    • Priority 값에 상관없이 Key들이 무작위(random)으로 저장.
    • Delete 연산은 매우 비효율적; O(n)
      • 처음부터 마지막까지 다 찾아봐야 함.
      • Linear Search를 이용함.
    • Insert 연산은 매우 효율적; O(1)
      • 새로운 key를 무조건 array의 맨 끝에 넣으면 됨.
      • 데이터 이동이 발생하지 않음.


  • Ordered Array를 이용
    • Priority 값을 기준으로 key들을 오름차순으로 정렬
    • Priority 값이 가장 큰 key는 항상 array의 맨 끝에 위치함.
    • Delete 연산은 매우 효율적; O(1)
    • Insert 연산은 매우 비효율적; O(n)
      • 새로운 key를 삽입할 때 항상 올바른 위치를 찾아서 넣어야 함. 이는 정렬상태를 유지해야 하기 때문.
      • Binary Search를 이용하여 삽입 위치를 찾음; O(log2n)
      • 삽입 후에 데이터 이동을 해야 함; O(n)


  • Unordered Linked List를 이용
    • (가정) ptr이라는 linked list의 맨 앞을 가리키는 pointer가 존재.
    • Priority 값에 상관없이 Key들이 무작위(random)으로 저장.
    • Delete 연산은 매우 비효율적; O(n)
      • 처음부터 마지막까지 다 찾아봐야 함.
      • Linear Search를 이용함; O(n)
    • Insert 연산은 매우 효율적; O(1)
      • 새로운 key 값을 list의 항상 맨 앞에 삽입
      • 데이터 이동 발생하지 않음


  • Ordered Linked List를 이용
    • Priority 값을 기준으로 key들을 내림차순으로 정렬
    • Priority 값이 가장 큰 key는 항상 맨 앞 node에 위치함.
    • Delete 연산은 매우 효율적; O(1)
    • Insert 연산은 매우 비효율적; O(n)
      • 새로 삽입되는 key 값을 올바른 위치에 넣어야 함.
      • Binary Search를 사용하기가 어려움;
      • 최악의 경우 맨 뒤에 삽입됨; O(n);


  • Binary Search Tree를 이용
    • Key들을 Binary Search Tree(BST)에 저장함.
    • Delete 연산은 비효율적;
      • 가장 큰 key를 찾기 위해, 오른쪽 방향으로 계속 내려감.
      • 시간은 BST의 height이고, 성능은 BST의 모양에 좌우됨
      • Worst : O(n), Average : O(log2 n)
    • Insert 연산은 비효율적;
      • 새로운 key 값이 항상 leaf node에 삽입됨.
      • 시간은 BST의 height이고, 성능은 BST의 모양에 좌우됨
      • Worst : O(n), Average : O(log2 n)


image


  • Max(Min) Heap이 가장 효율적임. 삽입과 삭제 모두 O(log2n) 보장
  • 예: n = 1,000일 경우 각 방법에 대해 시간 성능은? n = 1000,000?


Heap

  • Max Heap :
    • (1) Complete binary tree
    • (2) Key of each node is no smaller than its children’s keys


image


  • Min Heap :
    • (1) Complete binary tree
    • (2) key of each node is no larger than its children’s keys.


  • 차이점 : Max heap vs. BST

image


  • Examples : Max Heap

image

  • Root of a max heap always has the largest value


  • Examples : Not a Max Heap

image


  • Examples : Min Heap

image

  • Root* of a min heap always has the **smallest value.


Heap : Array로 구현

  • Heap을 array로 구현하는 이유
    • (Complete binary tree 이므로) space 낭비가 없음.
    • Parent와 child들의 위치를 찾기가 매우 쉬움
    • Link list와 같은 복잡한 pointer 연산이 필요 없음.
  • Finding a node location
    • Left-Child(i) = 2i + 1
    • Right-Child(i) = 2i + 2
    • Parent(i) = $\lfloor$ (i - 1) / 2 $\rfloor$ (if i = 0, i is the root)


image

  • heap에서 node 의 parent, left child, right child는?


  • Array 표현 : Max Heap

image


Max (Min) Heap 연산

  • Find-Max (Find-Min) : O(1)
    • Largest (smallest) Key를 Max (Min) Heap에서 찾아 return;
  • Insert : O(log2n)
    • 새로운 key를 Max (Min) Heap에 삽입
  • Delete : O(log2n)
    • Largest (smallest) Key를 Max (Min) Heap에서 찾아 삭제;
  • Sort : O(nlog2n)
    • Key들을 올림 차순 (혹은 내림 차순)으로 정렬하여 출력


Insert : Max Heap

  • Step 1 :
    • (1) Insert a new key into max heap;
    • (2) Insert 위치는? : 마지막 leaf node 바로 다음의 빈 공간;
    • (Why? : condition (1)을 만족하기 위해)
  • Step 2 :
    • (1) Compare the new key with its parent;
    • (2) If it is larger than the parent, swap it with the parent.
    • Repeat step 2 until heap condition (2) is satisfied.
    • Step 2 is called Reheap-Up


image

  • Find an empty location; This is a node which is right next of the last leaf node.


Case 1

image

  • Suppose we insert 5;
  • This case is very simple; Just insert it.


Case 2

image

  • Suppose we insert 20.
  • Compare 20 with its parent (7).


image

  • Since 20 > 7, swap 20 and 7; 즉, Move 20 Up.
  • Compare 20 with its parent (8).


image

  • Since 20 > 8, swap 20 and 8; 즉, Move 20 up again.
  • Compare 20 with its parent (9).


image

  • Since 20 > 9, swap 20 and 9; Move 20 up again.
  • Since this node is root, the insertion is done.


Delete : Max Heap

  • Step 1 :
    • (1) Find largest key and remove it.
    • (2) Largest key는 항상 root에 있음; (remove 순간, root는 empty)
  • Step 2 :
    • (1) Find a key (say, L) in last leaf node and insert L into root.
    • (2) Delete the last leaf node.
  • Step 3 :
    • (1) Compare L with its children.
    • (2) If one of children is larger, swap L with the larger child.
    • Repeat step 3 until heap condition (2) is satisfied.
    • Step 3 is called Reheap-Down


image

  • Find the largest key;
  • This key (20) is always in the root.


image

  • After largest key (20) is removed, root is empty


image

  • Find the last leaf node; This contains 8.
  • Delete this node from a heap; Then, there are 10 nodes


image

  • To reinsert 8 into the heap, initially, store 8 at the root.
  • Compare 8 with its child node with larger value; This is 15


image

  • Since 8 < 15, swap 8 and 15; Move 8 down.
  • Compare 8 with its child node with larger value; This is 9.


image

  • Since 8 < 9, swap 8 and 9; Move 8 down.
  • Compare 8 with its child node with larger value; This is 7.
  • Since 8 < 7, the deletion is done


image

  • 1) 위의 Max Heap을 array로 표현하라.
  • 2) 위의 Max Heap에서 3번 연속 delete한 후 상태를 array는?


시간 분석 : Insert/Delete

  • Insertion / deletion time is bounded by height of a heap.
  • What is a height of heap? : O(log2n)
  • 높이가 h인 Heap에서 node들의 최대/최소 개수는?
  • (특히) Binary tree의 모든 각 node에서 왼쪽 subtree와 오른쪽 subtree의 높이 차이가 1 이하이면, 이를“Balanced” 라 함.
  • 모든 Balanced Binary tree의 높이는 항상 log2 (n+1).
  • Complete binary tree는 이러한 것들의 대표적인 유형.


Max Heap 응용 : Sort

  • Max Heap을 이용하여 n 개의 key들을 올림 차순으로 sort하라.
    • 예 : {40, 35, 20, 45, 60, 30, 25}
  • 알고리즘(스케치):
    • 1) Build a max heap from unsorted array;
    • 2) Delete (the largest key) from max heap;
    • 3) Put it at the end of array
    • Repeat 2) and 3) n times
    • 위 알고리즘의 시간 분석을 하라.


Max Heap : 연습

  • Find $k^{th}$ largest key from an unsorted array with size n;
    • 방법 1 : Sort and select element at location k
    • 방법 2 : Build max heap and delete k times
    • : 위 각 방법에 대해 시간 분석을 하여라.
  • 다음의 key들을 차례대로 insert한 후의 max (혹은 min) heap을 array 상태로 단계별로 보여라.
    • 예시 1 : {20, 25, 10, 30, 15, 35, 40, 45}
    • 예시 2 : {10, 15, 20, 25, 30, 35, 40, 45}
    • 예시 3 : {45, 40, 35, 30, 25, 20, 15, 10}

댓글남기기